The present invention is related to computer programming, and more particularly to the use of recovery code to recover from incorrect speculation.
Even as processor speeds increase into the gigahertz range, there is an increased realization that speed alone will not provide adequate performance. Designers are therefore turning to processor architectures which execute two or more instructions per clock cycle (IPC). Superscalar processors and very-long-instruction-word (or VLIW) processors are two examples of processors capable of executing two or more instructions per clock cycle.
Compilers can be designed to exploit efficiencies inherent in a processor having an IPC of greater than one. For instance, a compiler may search during compile time for instructions which can be executed in parallel and may even reorder instructions within the program to enhance parallel execution. Sometimes, the compiler may speculate as to a control path (control speculation) or a data value (data speculation). In these cases, the compiler should provide a way to recover from incorrect speculation.
One approach to recover from compiler-controlled speculation is to provide a recoverable interval of instructions in the object code (called xe2x80x9crecovery codexe2x80x9d) for the processor to execute in the case of failed speculation. This interval of instructions is essentially a copy of the thread of computation which was previously executed speculatively. This implies that the compiler must update the instructions in this recovery code as it speculates loads and their subsequent uses. The bookkeeping for this task is further complicated in that not all uses of a speculative load may execute speculatively. Adding recovery code also complicates optimization in that it adds control flow to the optimization scope. This may prove too difficult or expensive to update for many optimizations since dependence information is built atop control flow information.
One such recovery approach can be described as consisting of two phases. The first phase is during scheduling when a load is speculated. The successors of the load are visited in topological order computing a live-set of values which may be upwards exposed uses in the recoverable interval. These are those values that will be live into the recovery code for the load""s recovery check. This is conservative in that it assumes that all uses of the speculative value will move above the check.
Such an approach can lead to poor performance. For instance, in the case of the following conservative line interval calculation:
ld.a r32=
chk.a r32,
ld r34=[a]
add r33=r34,r32
the load ofxe2x80x9cr32xe2x80x9d speculates and leaves a check behind. (In this example, xe2x80x9cldxe2x80x9d is a load instruction, xe2x80x9cld.axe2x80x9d is a speculative load instruction and xe2x80x9cchk.axe2x80x9d is a check on the speculative load instruction.) The successors of the load are visited and the live-set of the recovery interval is computed. In this case the xe2x80x9cadd r33=r34,r32xe2x80x9d adds the value xe2x80x9cr34xe2x80x9d to the live-set of the check. Since xe2x80x9cr34xe2x80x9d is now live into the check, the xe2x80x9cId r34=[a]xe2x80x9d can not move above the check because of a write-live dependence.
The second major phase involves generating the recovery for each check after instruction scheduling is completed. The speculative chains are identified and the flow dependencies are followed, adding instructions to the recovery code as each instruction is visited which topologically precedes the speculative load check. One major problem with generating recovery code in this manner is that it is difficult to combine control checks without effecting the schedule.
Another recovery code approach is described by William Yu-Wei Chen, Jr. in his Ph.D. thesis entitled Data Preload for Superscalar and VLIW Processors, University of Illinois at Urbana-Champaign, 1993. Chen teaches that a memory conflict buffer (or MCB) can be used to track and correct cases where a load from a memory location is moved above a store to the same location. In one approach, a conflict bit is associated with each general purpose register. At each preload, the location from which the preload is read is stored into an address register corresponding to the destination register of the preload. On a store, a comparison is made to the addresses stored in each of the address registers. If there is a match, the conflict bit corresponding to the general destination register is set. A subsequent check instruction notes the conflict bit and branches to the recovery code.
Neither of the approaches described above addresses the problem of handling recovery code coming to the instruction scheduler from other phases in the compiler. That is, if an earlier phase of compilation were to also exploit hardware based speculation and construct recovery code, the scheduler cannot simply reconstruct all recovery code from scratch (i.e. it must honor the recovery code which came to it). This can be complicated by the fact that an instruction scheduler""s local analysis may not be able to determine the extent of a speculative lifetime and the relationships between subsequent uses. In other words, local analysis might not be aware of when a use of a speculative value is crossing a check that checks the use""s operands. An example is shown below for a local lifetime analysis code fragment:
ld.a r32=
add r33=1,r32
while (! change) do
ld r34=
chk.a r32, rec 1
xor r35=r33,r34
od;
Since most instruction schedulers would not include the loop region and the region outside of the loop together, an instruction scheduler would only include the entire loop body as a single region at best. Because of this, it is difficult to know that the xe2x80x9cxorxe2x80x9d inside the loop is reading a speculative value that is being checked by the xe2x80x9cchk.a r32xe2x80x9d before it.
What is needed is a system and method for dynamically creating and updating control and data speculative recovery code during more than one phase of compilation, including the instruction scheduling phase.
According to one aspect of the present invention, a system and method of compiling source code is described which generates intermediate code from the source code, generates object code instructions from the intermediate code and schedules the object code instructions. Object code instructions are scheduled by inserting a speculation check into the object code instructions, storing recovery code associated with the speculation check and generating a control flow graph. The control flow graph is generated by converting the speculation check to a non-flow control check instruction, attaching one or more pseudo instructions to the check instruction and converting the non-flow control check instruction to a flow control check instruction, wherein the pseudo instructions represent recovery code behavior for the recovery code associated with the check instruction.